package uf;

/**
 * 并查集结构 树形
 */
public class UF_Tree {
    private int[] elementAndGroup;
    private int count;

    public UF_Tree(int N) {
        this.count = N;
        this.elementAndGroup = new int[N];

        for (int i = 0; i < elementAndGroup.length; i++) {
            elementAndGroup[i] = i;
        }
    }

    public int count() {
        return count;
    }

    private int find(int p) {
        while (true) {
            if (p == elementAndGroup[p]) {
                return elementAndGroup[p];
            }
            p = elementAndGroup[p];
        }

    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) {
            return;
        }

        elementAndGroup[pRoot] = qRoot;

        count--;

    }


}
